package top.datacluster.basic.algorithm.leetcode.heap;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class LeetCode264 {

    public int nthUglyNumber(int n) {
        PriorityQueue<Long> queue = new PriorityQueue<>();
        Map<Long, Long> data = new HashMap<>();
        queue.offer(1L);
        long result = 1L;
        for (int i = 0; i < n; i++){
            long temp = queue.poll();
            if (!data.containsKey(temp * 2)){
                queue.offer(temp * 2);
                data.put(temp* 2, temp * 2);
            }
            if (!data.containsKey(temp * 3)){
                queue.offer(temp * 3);
                data.put(temp* 3, temp * 3);
            }
            if (!data.containsKey(temp * 5)){
                queue.offer(temp * 5);
                data.put(temp* 5, temp * 5);
            }

            result = temp;
        }
        return (int)result;

    }

    public static void main(String[] args) {
        System.out.println(new LeetCode264().nthUglyNumber(1407));
    }
}
